package company.bytedance

import kotlinetc.println
import leetcode.pop
import leetcode.push
import tree.TreeNode
import java.util.*
import kotlin.collections.ArrayList

fun main(args: Array<String>) {


    val treeNode = TreeNode(
            "1",
            TreeNode("2",
                    TreeNode("4"), TreeNode("5")),
            TreeNode("3",
                    TreeNode("6"), TreeNode("7")))

    traversalLevelTree(treeNode).println()

}


fun traversalLevelTree(tree: TreeNode): ArrayList<ArrayList<String>> {


    val backUpStack = arrayListOf<TreeNode>()

    val stack = arrayListOf<TreeNode>()

    val result = arrayListOf<ArrayList<String>>()

    stack.push(tree)

    var nodeList = arrayListOf<String>()

    while (stack.isNotEmpty()) {

        val node: TreeNode = stack.first()

        stack.remove(node)

        if (node.left != null)
            backUpStack.add(node.left!!)

        if (node.right != null)
            backUpStack.add(node.right!!)
        nodeList.add(node.value)


        if (stack.isEmpty() && backUpStack.isNotEmpty()) {
            result.add(nodeList)
            nodeList = arrayListOf()
            stack.addAll(backUpStack)
            backUpStack.clear()
        }

    }

    result.add(nodeList)

    return result
}

/**
 * find the miminal size of contiguous subArray that sum large the the given number
 */
fun minimalSizeSubarray(nums: Array<Int>, s: Int): Int {

    if (nums.isEmpty() || (nums.size == 1 && nums.first() < s))
        return 0

    var s = 0

    var p = 0

    var sum = nums[s]

    var r = nums.size
    while (p <= nums.lastIndex) {

        if (sum < s) {
            p++
            sum += nums[p]
        } else {

            s++
            p++
            sum -= nums[s]
            sum += nums[p]
        }
    }
    return r
}